package top.houry.linklist;

import java.util.HashMap;
import java.util.Map;

/**
 * @Desc
 * @Author houruiyang
 * @Date 2022/9/6
 **/
public class LinkedListPointer {

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


    public Node randPointer(Node head) {
        if (null == head) {
            return head;
        }
        Map<Node, Node> map = new HashMap<>();

        Node dummy = new Node(-1);
        Node newHead = head;

        while (null != newHead) {
            Node newNode;
            if (map.containsKey(newHead)) {
                newNode = map.get(newHead);
            } else {
                newNode = new Node(newHead.val);
                map.put(newHead, newNode);
            }
            dummy.next = newNode;

            if (null != newHead.random) {
                Node random = newHead.random;
                if (map.containsKey(random)) {
                    newNode.random = map.get(random);
                } else {
                    Node newRand = new Node(random.val);
                    map.put(random, newRand);
                    newNode.random = newRand;
                }

            }
            dummy = newNode;
            newHead = newHead.next;
        }

        return map.get(head);

    }


    public Node a(Node head) {

        if (null == head) {
            return head;
        }

        Node newHead = head;
        Node dummy = new Node(-1);
        Map<Node, Node> map = new HashMap<>();


        while (null != newHead) {
            Node newNode;
            if (map.containsKey(newHead)) {
                newNode = map.get(newHead);
            } else {
                newNode = new Node(newHead.val);
                map.put(newHead, newNode);
            }
            dummy.next = newNode;
            if (null != newHead.random) {
                Node rand = newHead.random;
                if (map.containsKey(rand)) {
                    newNode.random = map.get(rand);
                } else {
                    Node copyRand = new Node(rand.val);
                    newNode.random = copyRand;
                    map.put(rand, copyRand);
                }
            }

            dummy = newNode;
            newHead = newHead.next;

        }

        return map.get(head);

    }


    public Node two(Node head) {

        copyNext(head);
        copyRandom(head);

        return split(head);

    }

    public void copyNext(Node head) {
        while (null != head) {
            Node node = new Node(head.val);
            // 临时变量需要有，记录方便下次使用
            Node next = head.next;
            head.next = node;
            node.next = next;

            head = next;
        }
    }

    public void copyRandom(Node head) {
        while (null != head) {
            Node random = head.random;
            if (null != random) {
                head.next.random = random.next;
            }
            head = head.next.next;
        }
    }

    public Node split(Node head) {
        Node newHead = head.next;
        while (null != head) {
            Node temp = head.next;
            head.next = temp.next;
            head = head.next;
            if (null != temp.next) {
                temp.next = temp.next.next;
            }

        }

        return newHead;
    }


    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        System.out.println("====");

    }

}
